package com.mamingchao.issue.binaryTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 用递归和非递归两种方式实现二叉树的先序、中序、后序遍历
 * Created by mamingchao on 2024/7/23.
 */
public class BinaryTreeIterator {

    public static void main(String[] args) {
        TreeNode node = buildTestTree();

        inOrderRecurse(node);
        System.out.println("-----------------");
        inOrderNotRecurse(node);

    }

    /**
     * 递归 先序遍历
     */
    public static void preOrderRecurse(TreeNode head){
        if (head == null)
            return;

        System.out.print(head.getKey() + " ");
        preOrderRecurse(head.leftChild);
        preOrderRecurse(head.rightChild);

    }

    /**
     * 非递归 先序遍历
     */
    public static void preOrderNotRecurse(TreeNode head){
        if (head == null)
            return;

        Stack<TreeNode> stack = new Stack<>();
        stack.add(head);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.println(node.getValue());

            if (node.rightChild != null) {
                stack.push(node.rightChild);
            }

            if (node.leftChild != null) {
                stack.add(node.leftChild);
            }
        }
    }

    /**
     * 递归 中序遍历
     */
    public static void inOrderRecurse(TreeNode head){
        if (head == null)
            return;

        inOrderRecurse(head.leftChild);
        System.out.print(head.getValue() + " ");
        inOrderRecurse(head.rightChild);
    }


    /**
     * 中序非递归方式
     * 把树的左边界 都放到栈里面去；左边界到底之后，依次弹出，每次弹出的时候，如果右孩子，右孩子的子树 也执行 刚刚的逻辑【左边界压栈到底，依次弹出，再弄右孩子】
     * @param head 树的头节点
     */
    public static void inOrderNotRecurse(TreeNode head){
        if (head == null)
            return;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        // 树的左边界，压栈到底
        while (head.leftChild != null){
            stack.push(head.leftChild);
            head = head.leftChild;
        }

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.println(node.getValue());
            if (node.rightChild != null) {
                node = node.rightChild;
                stack.push(node);
                while (node.leftChild != null){
                    stack.push(node.leftChild);
                    node = node.leftChild;
                }
            }
        }
    }

    /**
     * 递归 后序遍历
     */
    public static void postOrderRecurse(TreeNode head){
        if (head == null)
            return;

        postOrderRecurse(head.leftChild);
        postOrderRecurse(head.rightChild);
        System.out.print(head.getValue() + " ");
    }

    /**
     * 非递归后续遍历
     * 先序顺序 反着来，就是后续； 这里 在先序 打印的时候不打印，存辅助栈；再遍历把辅助栈中的数据打印出来，即为 后续
     * @param head
     * @return
     */
    public static void postOrderNotRecurse(TreeNode head){
        if (head == null)
            return;

        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> reverseStack = new Stack<>();
        stack.add(head);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            reverseStack.push(node);

            if (node.leftChild != null) {
                stack.add(node.leftChild);
            }

            if (node.rightChild != null) {
                stack.push(node.rightChild);
            }
        }

        while (!reverseStack.isEmpty()) {
            System.out.println(reverseStack.pop().getValue());
        }
    }

    /**
     * 创建一个测试二叉树
     * @return
     */
    private static TreeNode buildTestTree(){
        Queue<TreeNode> queue = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            TreeNode node = new TreeNode(i , "");
            queue.add(node);
        }

        TreeNode head = queue.poll();
        TreeNode trueHead = head;
        int i = 0;

        while (!queue.isEmpty()) {

            head.leftChild = queue.poll();
            head.rightChild = queue.poll();
            i ++;

            if (i%2==0){
                head = head.leftChild;
            } else {
                head = head.rightChild;
            }
        }

        return trueHead;
    }
}
